# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/4/15 21:42
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : BinarySearchTree.py
@Version     : Version 1.0.0
@Description : TODO 实现二叉搜索树类，结点类，插入方法，三种遍历方法
@Created By  : PyCharm
"""


# 定义BST结点类
class BinarySearchTreeNode(object):
    def __init__(self, parent, key):
        self.key = key
        self.parent = parent
        self.left = self.right = None

    def insert(self, key):
        """
        BST结点插入方法
        :param key: 结点数据
        :return: 插入结点
        """
        # if abs(key - self.key) < 3:
        #     print("Insert Error!")
        #     return
        if key < self.key:
            if self.left is None:
                self.left = BinarySearchTreeNode(self, key)
                # 当前结点引用self做parent，结点数据key存放在左子节点
                return self.left
            else:
                return self.left.insert(key)
        else:
            if self.right is None:
                self.right = BinarySearchTreeNode(self, key)
                # 当前结点引用self做parent，结点数据key存放在右子节点
                return self.right
            else:
                return self.right.insert(key)


# 定义BST类
class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def pre_root_traverse(self, node: BinarySearchTreeNode):
        """
        先根遍历二叉搜索树
        :param node: 开始遍历结点
        :return: 遍历序列
        """
        if node is not None:
            print(node.key, end="")
            self.mid_root_traverse(node.left)
            self.mid_root_traverse(node.right)

    def mid_root_traverse(self, node: BinarySearchTreeNode):
        """
         中根遍历二叉搜索树
         :param node: 开始遍历结点
         :return: 遍历序列
         """
        if node is not None:
            self.mid_root_traverse(node.left)
            print(node.key, end="")
            self.mid_root_traverse(node.right)

    def post_root_traverse(self, node: BinarySearchTreeNode):
        """
         后根遍历二叉搜索树
         :param node: 开始遍历结点
         :return: 遍历序列
         """
        if node is not None:
            self.mid_root_traverse(node.left)
            self.mid_root_traverse(node.right)
            print(node.key, end="")

    def delete_node(self, root: BinarySearchTreeNode, key):
        """
        删除BST中的任意一个结点
        :param root: BST根结点
        :param key: 待删除结点数据
        :return: 更新后的根结点
        """
        # 树为空
        if root is None:
            return None
        # 找到 key，进行删除
        if root.key == key:
            # 情况 1：两个子节点都为空
            # 情况 2：只有一个非空子节点，让这个孩子取代自己
            if root.left is None:
                return root.right
            if root.right is None:
                return root.left
            # 情况 3：有两个非空子节点，找到左子树的最大值，或者右子树的最小值，取代自己
            min_node = self.get_min(root.right)
            root.key = min_node.key
            root.right = self.delete_node(root.right, min_node.key)
        # key 在左子树
        elif root.key > key:
            root.left = self.delete_node(root.left, key)
        # key 在右子树
        elif root.key < key:
            root.right = self.delete_node(root.right, key)
        return root

    @staticmethod
    def get_min(root: BinarySearchTreeNode):
        """
        实现查找BST最小值结点算法
        :param root: BST根结点
        :return: 最小值结点
        """
        # BST 最左边的是最小值
        while root.left is not None:
            root = root.left
        return root


if __name__ == '__main__':
    char_seq = ["E", "A", "S", "Y", "Q", "U", "E", "S", "T", "I", "O", "N"]
    binary_search_tree = BinarySearchTree()  # 初始化二叉搜索树
    binary_search_tree.root = BinarySearchTreeNode(None, char_seq[0])  # 构造根结点
    # 构造二叉搜索树
    for char in char_seq:
        binary_search_tree.root.insert(char)
    # 中根遍历输出，这个情况为按照字符ASCII先后顺序有序输出
    # AEEEINOQSSTUY
    print("BST中根遍历序列为:", end="")
    binary_search_tree.mid_root_traverse(binary_search_tree.root)
    # 查找最小值结点
    minNode = binary_search_tree.get_min(binary_search_tree.root)
    print("\nBST最小值结点为:{}\n最小值为:{}".format(minNode, minNode.key))
    # 删除值为key="O"的结点
    binary_search_tree.delete_node(binary_search_tree.root, "O")
    # 删除后中根遍历输出
    # AEEEINQSSTUY
    print("BST删除结点值O后中根遍历序列为:", end="")
    binary_search_tree.mid_root_traverse(binary_search_tree.root)
